package a2_p04_jw_kw.searchalgo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.NeighborIndex;
import org.jgrapht.event.VertexTraversalEvent;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.DirectedPseudograph;

import a1_p04_jw_kw.graph.GraphUtility;
import a1_p04_jw_kw.struct.Node;

public class AStar {
	private static double INFINITE = 99999999.0;

	HashMap<Node, Double> distances = new HashMap<Node, Double>();
	HashMap<Node, Double> pathlength = new HashMap<Node, Double>();
	HashMap<Node, Double> heuristics = new HashMap<Node, Double>();
	HashMap<Node, Node> parentList = new HashMap<Node, Node>();
	HashMap<Node, Boolean> okI = new HashMap<Node, Boolean>();
	
	ArrayList<Node> openList = new ArrayList<Node>();
	ArrayList<Node> closeList = new ArrayList<Node>();
	
	int count = 0;

	Graph<Node, DefaultWeightedEdge> g;
	Node start;
	Node target;

	public AStar(Graph<Node, DefaultWeightedEdge> g,
			String start, String target) {
		this.g = g;
		this.start = GraphUtility.getNode(g, start);
		this.target = GraphUtility.getNode(g, target);

		this.initialize();
		this.start();
	}

	// initialize the astar
	private void initialize() {
		for (Node n : this.g.vertexSet()) {
			this.distances.put(n, 0.0);
			//this.pathlength.put(n, 0.0);
			this.parentList.put(n, null);
			this.heuristics.put(n, 0.0);
			this.okI.put(n, false);
				
		}
		
		// set values to the starting vertex
		this.distances.put(this.start, 0.0);
		this.pathlength.put(this.start, 0.0);
		this.parentList.put(this.start, null);
		this.heuristics.put(this.start, this.distances.get(this.start) + this.start.attribute);	
		
		this.openList.add(this.start);
		
		
	}

	private void start() {
//		while (okI.get(target) == false) {
//			count ++;
//			
//			// getNextVertex
//			Node currentVertex = getNextVertexToExamine();
//			// set vertex as examined
//			okI.put(currentVertex, true);
//
//			// for all unexamined successors
//			for (Node n : getUnexaminedSuccesors(currentVertex)) {
//				// if current length to the unexaminedSuccessor is higher then
//				// the length of the current vertex + the weight of the edge to
//				// the unexaminedSuccesor, set a new length 
//				double lengthToUnexaminedSuccessor = distances.get(currentVertex) + g
//						.getEdgeWeight(g.getEdge(currentVertex, n)) + heuristics.get(n);
//				
//				if (distances.get(n) > lengthToUnexaminedSuccessor) {
//					
//					double length = pathlength.get(currentVertex) + g
//							.getEdgeWeight(g.getEdge(currentVertex, n));
//					
//					distances.put(n,((Double)lengthToUnexaminedSuccessor));
//					pathlength.put(n,((Double)length));
//					parentList.put(n, currentVertex);
//				}
//			}
//		}
		
		
		while (!this.openList.isEmpty()) {
			count ++;
			
			// getNextVertex
			Node currentVertex = getNextVertexToExamine();			
			
			if (currentVertex.equals(this.target)) {
				break;
				
			}
			
			this.openList.remove(currentVertex);
			this.closeList.add(currentVertex);
			
			for (Node n : getSuccesors(currentVertex)) {
				if (this.closeList.contains(n)) {
					continue;
					
				}
				
				double tentativeScore = this.distances.get(currentVertex) + g.getEdgeWeight(g.getEdge(currentVertex, n));
				if ((!this.openList.contains(n)) || tentativeScore <= this.distances.get(n)) {
					this.parentList.put(n, currentVertex);
					this.distances.put(n, tentativeScore);
					this.heuristics.put(n, this.distances.get(n) + n.attribute);
					if (!this.openList.contains(n)) {
						this.openList.add(n);
						
					}
					
				}
				
			}
			
			
		}
	}

	// gets the node from the openlist with the lowest f value
	private Node getNextVertexToExamine() {
		Node vertexWithLowestValue = null;
		double lowestValue = INFINITE;

		
		for (Node n : this.openList) {
			if (vertexWithLowestValue == null) {
				vertexWithLowestValue = n;
				lowestValue = this.heuristics.get(n);
				
			}
			
			if (this.heuristics.get(n) < lowestValue) {
				vertexWithLowestValue = n;
				lowestValue = this.heuristics.get(n);
				
			}
			
		}
			
		return vertexWithLowestValue;
	}

	private boolean isExamined(Node node) {
		if (okI.get(node)) {
			return true;
		}
		return false;
	}

	private boolean hasUnexaminedVertices() {
		for (Map.Entry<Node, Boolean> entry : this.okI.entrySet()) {
			if (!entry.getValue()) {
				return true;
			}
		}
		return false;
	}

	// return all unexamined successors
	private ArrayList<Node> getSuccesors(Node node) {
		ArrayList<Node> unexaminedSuccesors = new ArrayList<Node>();

		// get all successors and check if they are already examined
		for (Node n : Graphs.neighborListOf(this.g, node)) {
			unexaminedSuccesors.add(n);
			
		}
		return unexaminedSuccesors;
	}
	
	public double getLenghtToTarget() {
		return this.distances.get(GraphUtility.getNode(this.g, target.name));
	}
	
	public ArrayList<Node> getBestWayToTarget() {
		Node n = GraphUtility.getNode(this.g, target.name);
		ArrayList<Node> bestWay = new ArrayList<Node>();
		
		bestWay.add(n);		
		
		while (!n.equals(this.start)) {
			Node predeccessor = parentList.get(n);
			bestWay.add(predeccessor);
			n = predeccessor;
		}
		return bestWay;
	}
	
	public int getCount() {
		return count;
	}

	public HashMap<Node, Double> getDistances() {
		return distances;
	}

	public HashMap<Node, Double> getHeuristics() {
		return heuristics;
	}

	public HashMap<Node, Node> getParentList() {
		return parentList;
	}

	public HashMap<Node, Boolean> getOkI() {
		return okI;
	}

	public HashMap<Node, Double> getPathlength() {
		return pathlength;
	}	
}
